package ljl.alg.wangzheng_camp.round1.backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _40_combination_sum {
    
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    List<int[]> freq = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        for (int each : candidates) {
            int size = freq.size();
            if (size == 0 || freq.get(size - 1)[0] != each)
                freq.add(new int[] {each, 1});
            else
                freq.get(size - 1)[1]++;
        }
        dfs(0, target);
        return res;
    }
    void dfs(int pos, int remaining) {
        if (remaining == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        else if (pos == freq.size() || freq.get(pos)[0] > remaining) return;
        dfs(pos + 1, remaining);
        int value = freq.get(pos)[0], count = freq.get(pos)[1];
        int max = Math.min(remaining / value, count);
        for (int i = 1; i <= max; i++) {
            path.add(value);
            dfs(pos + 1, remaining - i * value);
        }
        for (int i = 0; i < max; i++) {
            path.remove(path.size() - 1);
        }
    }
    
    class Solution {
        List<int[]> freq = new ArrayList<int[]>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> sequence = new ArrayList<Integer>();
        
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            Arrays.sort(candidates);
            for (int num : candidates) {
                int size = freq.size();
                if (freq.isEmpty() || num != freq.get(size - 1)[0]) {
                    freq.add(new int[]{num, 1});
                } else {
                    ++freq.get(size - 1)[1];
                }
            }
            dfs(0, target);
            return ans;
        }
        
        public void dfs(int pos, int rest) {
            if (rest == 0) {
                ans.add(new ArrayList<Integer>(sequence));
                return;
            }
            if (pos == freq.size() || rest < freq.get(pos)[0]) {
                return;
            }
            
            dfs(pos + 1, rest);
            
            int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);
            for (int i = 1; i <= most; ++i) {
                sequence.add(freq.get(pos)[0]);
                dfs(pos + 1, rest - i * freq.get(pos)[0]);
            }
            for (int i = 1; i <= most; ++i) {
                sequence.remove(sequence.size() - 1);
            }
        }
    }
}
